package offerv1;

public class Offer33 {

    //后序遍历 左子树|右子树|根节点
    //最后一个元素是根节点
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    //数组 左 右
    //左边[i,m-1] 根节点j [m,j-1]
    //postorder[j]当前根节点
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;//单调递增
        int m = p;
        while(postorder[p] > postorder[j]) p++;//单调递减
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}
